package com.zjsru.binaryeasy;

/**
 * @Author: likew
 * @Date: 2022/8/6
 * 第 k 个缺失的正整数
 *
 * 给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
 *
 * 请你找到这个数组里第 k 个缺失的正整数。
 *
 * 输入：arr = [2,3,4,7,11], k = 5
 * 输出：9
 * 解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。
 *
 */
public class FindKthPositive {
    public int findKthPositive(int[] arr, int k) {
        int missCount = 0, lastMiss = -1, current = 1, ptr = 0;
        for (missCount = 0; missCount < k; ++current) {
            if (current == arr[ptr]) {
                ptr = (ptr + 1 < arr.length) ? ptr + 1 : ptr;
            } else {
                ++missCount;
                lastMiss = current;
            }
        }
        return lastMiss;
    }
    
    public static void main(String[] args) {
        FindKthPositive findKthPositive = new FindKthPositive();
        int[] arr = new int[]{2,3,4,7,11};
        int k = 5;
        System.out.println(findKthPositive.findKthPositive(arr, k));
    }
}
